package demo.DataStrucAndAlgo.Sort;

import java.util.Arrays;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/7/27-07-27-19:17
 * @Description：demo.DataStrucAndAlgo.Sort      基数排序  桶排序扩展，属于稳定性排序算法
 */
/*
基数排序（不考虑负数）
    思想：
        将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。
     这样从最低位排序一直到最高位排序完成以后，数列就变成了一个有序序列
    过程：
        第一轮排序：
            将每个元素的个位数取出，然后看这个数应该放在哪个对应的桶（一个一维数组）
            按照这个桶的顺序（一维数组的下标依次取出数据，放入原来数组）
        第二轮排序：
            将每个元素的十位数取出，然后看这个数应该放在哪个对应的桶（一个一维数组）
            按照这个桶的顺序（一维数组的下标依次取出数据，放入原来数组）
        第三轮排序：
            将每个元素百位数取出，然后看这个数应该放在哪个对应的桶（一个一维数组）
            按照这个桶的顺序（一维数组的下标依次取出，放入原来数组）
 */
public class RadixSort {
    public static void main(String[] args) {
        int data[] = {8,4,5,7,1,3,6,2};
        radixSort(data);
        System.out.println(Arrays.toString(data));
    }

    public static void radixSort(int[] data) {
        //获取数据中最大数
        int max = data[0];
        for(int i = 1; i < data.length; i++){
            if(max < data[i]){
                max = data[i];
            }
        }
        //获取最大数位数
        int maxSize = (max+"").length();
        //创建一个桶数组
        int[][] bucket = new int[10][data.length];
        //创建一个桶计数数组，记录桶中的数据个数
        int[] bucketCount = new int[10];

        for (int i = 0, n = 1; i < maxSize; i++, n *= 10) {  //循环最高位数次
            for(int j = 0; j < data.length; j++){    //每轮排序一次
                int digit = data[j]/n%10;     //求得数据每轮的数位值
                bucket[digit][bucketCount[digit]] = data[j];
                bucketCount[digit]++;   //计数
            }
            //把桶中数据按顺序放回原数组
            int index = 0;  //用于操作原数组
            for (int k = 0; k < 10; k++) {
                //如果第k个桶有数据就开始放
                if(bucketCount[k]>0){
                    for (int j = 0; j < bucketCount[k]; j++) {
                        data[index] = bucket[k][j];    //将第k个桶中的全部数据依次放入原数组中
                        index++;
                    }
                }
                bucketCount[k] = 0;
            }
        }
    }
}
